package heapsort;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/13 1:29
 * 堆排序
 * 时间复杂度 O(nlog n)
 */
public class HeapSort {

    /**
     * 接收一个数组, 构造大根堆, 不断缩小范围, 交换堆顶和末尾元素并向下调整, 直到使其正序
     * @param arr 源数据
     */
    public static void heapSort(int[] arr) {
        if (arr == null) {
            return;
        }
        int len = arr.length;
        // 构造大根堆
        createMaxHeap(arr, len);
        System.out.println("[createMaxHeap] 大根堆: arr=" + Arrays.toString(arr));
        // 每次交换堆顶与末尾元素, 并向下调整, 不断缩小范围
        int end = len - 1;
        while (end > 0) {
            int temp = arr[end];
            arr[end] = arr[0];
            arr[0] = temp;
            shiftDown(arr, 0, end);
            end--;
        }
    }

    /**
     * 构造大根堆
     */
    private static void createMaxHeap(int[] arr, int len) {
        if (arr == null) {
            return;
        }
        // 从最后一个 parent 开始向下调整
        for (int parent = (len - 2) / 2; parent >= 0; parent--) {
            shiftDown(arr, parent, len);
        }
    }

    /**
     * 建堆过程向下调整
     */
    private static void shiftDown(int[] arr, int parent, int len) {
        if (arr == null) {
            return;
        }
        int child = 2 * parent + 1; // 左孩子
        while (child < len) {
            if (child + 1 < len && arr[child + 1] > arr[child]) {
                child = child + 1; // 保证 child 指向兄弟节点的较大值
            }
            if (arr[child] > arr[parent]) {
                // 与父亲节点交换后继续向下调整
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {100, 32, 3, 6, 24, 86, 23, 90, 78, 3};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
